package com.example.demo.arithmetic.datastructure.linkedlist2;

/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 * <p>
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下：
 * [
 * 1->4->5,
 * 1->3->4,
 * 2->6
 * ]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 * 示例 2：
 * <p>
 * 输入：lists = []
 * 输出：[]
 * 示例 3：
 * <p>
 * 输入：lists = [[]]
 * 输出：[]
 */
public class Leetcode23 {

    public static void main(String[] args) {
        ListNode head1 = new ListNode(9, null);
        ListNode head2 = new ListNode(8, head1);
        ListNode head3 = new ListNode(3, head2);
        ListNode list1 = new ListNode(1, head3);

        ListNode head5 = new ListNode(4, null);
        ListNode list2 = new ListNode(2, head5);

        ListNode head=  new Leetcode23().mergeKLists(new ListNode[]{list1,list2});
        while (head != null) {
            System.out.println(head.val);
            head = head.next;
        }

    }

    /**
     * 拆分为 合并 两个链表
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        return mergeKLists0(lists, 0, lists.length - 1);
    }

    private ListNode mergeKLists0(ListNode[] lists, int l, int r) {
        if (r == l) {
            return lists[r];
        }
        int mid = (r + l) >>> 1;
        ListNode left = mergeKLists0(lists, l, mid);
        ListNode right = mergeKLists0(lists, mid + 1, r);
        return mergeTwoLists(left, right);
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;
        return prehead.next;
    }
}
